public class QuickSort {
    //快速排序的主递归方法
    private static void quickSort(int[] arr, int left, int right) {
        // 数组为空或长度小于2不需要排序
        if (arr == null || arr.length < 2) {
            return;
        }
        // 子数组只有一个元素时停止分割
        if (left >= right) {
            return;
        }

        // 获取基准值的位置
        int pivot = partition(arr, left, right);

        // 递归排序基准值左边的子数组
        quickSort(arr, left, pivot - 1);
        // 递归排序基准值右边的子数组
        quickSort(arr, pivot + 1, right);
    }

     //分区操作 - 将数组分为两部分，左边小于基准值，右边大于基准值
    private static int partition(int[] arr, int left, int right) {
        // 选择最右边的元素作为基准值(pivot)
        int pivot = arr[right];
        // i指向小于基准值的区域的最后一个元素
        int i = left;

        // j指针遍历整个分区
        for (int j = left; j < right; j++) {
            // 如果当前元素小于基准值
            if (arr[j] < pivot) {
                // 将当前元素交换到小于基准值的区域
                swap(arr, i, j);
                // 扩大小于基准值的区域
                i++;
            }
        }
        // 将基准值放到正确的位置
        swap(arr, i, right);
        // 返回基准值的最终位置
        return i;
    }


     //交换数组中两个元素的位置

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {5, 2, 9, 1, 5, 6};
        System.out.println("排序前数组:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();

        // 调用快速排序
        quickSort(arr, 0, arr.length - 1);

        System.out.println("快速排序结果:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}